#ifndef MYVECTOR_H
#define MYVECTOR_H

//#include <iostream>
#include <assert.h>
#include <cstddef>
#include <iterator>
#include "myallocator.h"
#include <initializer_list>
#include <type_traits>

namespace mystl
{
    template <typename T, typename Allocator = mystl::allocator<T>>
    class vector{
    public:
        // redifine variable name
        typedef T value_type;
        typedef Allocator allocator_type;
        typedef std::size_t size_type;
        typedef std::ptrdiff_t difference_type;
        typedef value_type& reference;
        typedef const value_type& const_reference;
        typedef typename allocator_type::pointer pointer;
        typedef typename allocator_type::const_pointer const_pointer;
        typedef T *iterator;
        typedef const T *const_iterator;
        typedef std::reverse_iterator<iterator> reverse_iterator;
        typedef std::reverse_iterator<const_iterator> const_reverse_iterator; 
        
        // announcment of the functions
        //  iterators
        iterator begin();
        const_iterator begin() const;
        reverse_iterator rbegin();
        const_reverse_iterator rbegin() const;
        //const_iterator cbegin() const noexcept;
        iterator end();
        const_iterator end() const;
        reverse_iterator rend();
        const_reverse_iterator rend() const;

        // element access
        reference operator[](size_t i);
        const_reference operator[](size_t i) const;
        iterator data();
        const_iterator data() const;
        reference at( size_type pos );
        const_reference at( size_type pos ) const;
        reference front();
        const_reference front() const;
        reference back();
        const_reference back() const;

        // construct and deconstruct
        vector();
        vector(const vector<value_type> &v);
        vector(const size_t n, const value_type& x = value_type());

        template<class InputIt, typename std::enable_if<std::is_pointer<InputIt>::value, int>::type = 0>
        vector(InputIt first, InputIt last);

        vector(vector &&other) noexcept;
        
        vector(std::initializer_list<T> init);
        ~vector();

        //other functions
        template <class InputIt, typename std::enable_if<std::is_pointer<InputIt>::value, int>::type = 0>
        void assign(InputIt first, InputIt last);

        void assign(size_type count, const T& value);

        // capacity and size
        bool empty() const;
        size_t capacity() const;
        size_t size() const;
        void resize(size_t newsize, value_type x = 0);
        void reserve(size_t n);
        void shrink_to_fit();

        // adjust the elements
        void pop_back();
        void push_back(const value_type &x);
        iterator insert(iterator pos, const value_type &x);
        iterator insert( iterator pos, size_type count, const T& value );
        
        template< class InputIt, typename std::enable_if<std::is_pointer<InputIt>::value, int>::type = 0>
        iterator insert( iterator pos, InputIt first, InputIt last );
        
        iterator erase(iterator pos);
        iterator erase( iterator first, iterator last );
        void clear();
        // template< class... Args >
        // void emplace_back( Args&&... args );
        template< class... Args >
        reference emplace_back( Args&&... args );

        // new operator
        vector<value_type> &operator=(const vector<value_type> &v);
        vector<value_type>& operator=( std::initializer_list<value_type> ilist );
        bool operator==(const vector<value_type> &v);

        // swap two vectors
        void swap(vector<value_type> &v) noexcept;

    void construct(T *ptr)
    {
        ::new (ptr) T();
    }
    //
    void construct(T *ptr, const T &value)
    {
        ::new (ptr) T(value);
    }
    //
    void destroy(T *ptr)
    {
        ptr->~T();
    }
    //
    void destroy(T *first, T *last)
    {
        size_t n = last - first;
        assert(n >= 0);
        for (T* it = first; it != last; ++it)
        {
            it->~T();
        }
    }
    private:
        iterator m_start;
        iterator m_finish;
        iterator m_endofstorage;
        allocator_type m_allocator;
    };

    // definition of the functions

    template <typename T, typename Allocator>
    typename vector<T, Allocator>::iterator vector<T, Allocator>::begin()
    {
        return m_start;
    }

    template <typename T, typename Allocator>
    typename vector<T, Allocator>::const_iterator vector<T, Allocator>::begin() const
    {
        return m_start;
    }

    template <typename T, typename Allocator>
    typename vector<T, Allocator>::reverse_iterator vector<T, Allocator>::rbegin()
    {
        return reverse_iterator(m_finish);
    }

    template <typename T, typename Allocator>
    typename vector<T, Allocator>::const_reverse_iterator vector<T, Allocator>::rbegin() const
    {
        return reverse_iterator(m_finish);
    }    

    template <typename T, typename Allocator>
    typename vector<T, Allocator>::iterator vector<T, Allocator>::end()
    {
        return m_finish;
    }

    template <typename T, typename Allocator>
    typename vector<T, Allocator>::const_iterator vector<T, Allocator>::end() const
    {
        return m_finish;
    }

    template <typename T, typename Allocator>
    typename vector<T, Allocator>::reverse_iterator vector<T, Allocator>::rend()
    {
        return reverse_iterator(m_start);
    }
    
    template <typename T, typename Allocator>
    typename vector<T, Allocator>::const_reverse_iterator vector<T, Allocator>::rend() const
    {
        return reverse_iterator(m_start);
    }        
    // **********************************************************
    template <typename T, typename Allocator>
    typename vector<T, Allocator>::const_reference vector<T, Allocator>::operator[](size_t i) const
    {
        assert(i < size());
        return m_start[i];
    }
    //
    template <typename T, typename Allocator>
    typename vector<T, Allocator>::reference vector<T, Allocator>::operator[](size_t i)
    {
        assert(i < size());
        return m_start[i];
    }
    //
    template <typename T, typename Allocator>
    typename vector<T, Allocator>::iterator vector<T, Allocator>::data()
    {
        return m_start;
    }
    template <typename T, typename Allocator>
    typename vector<T, Allocator>::const_iterator vector<T, Allocator>::data() const
    {
        return m_start;
    }
    //
    template <typename T, typename Allocator>
    typename vector<T, Allocator>::const_reference vector<T, Allocator>::at(size_type i) const
    {
        assert(i < size());
        return m_start[i];
    }
    //
    template <typename T, typename Allocator>
    typename vector<T, Allocator>::reference vector<T, Allocator>::at(size_type i)
    {
        assert(i < size());
        return m_start[i];
    }
    //
    template <typename T, typename Allocator>
    typename vector<T, Allocator>::const_reference vector<T, Allocator>::front() const
    {
        assert(m_start < m_finish);
        return *m_start;
    }
    //
    template <typename T, typename Allocator>
    typename vector<T, Allocator>::reference vector<T, Allocator>::front()
    {
        assert(m_start < m_finish);
        return *m_start;
    }
    //
    template <typename T, typename Allocator>
    typename vector<T, Allocator>::const_reference vector<T, Allocator>::back() const
    {
        assert(m_start < m_finish);
        return *(m_finish-1);
    }
    //
    template <typename T, typename Allocator>
    typename vector<T, Allocator>::reference vector<T, Allocator>::back()
    {
        assert(m_start < m_finish);
        return *(m_finish-1);
    }

    // ********************************************
    // construct and deconstruct
    template <typename T, typename Allocator>
    vector<T, Allocator>::vector() : m_start(nullptr), m_finish(nullptr), m_endofstorage(nullptr), m_allocator()
    {
    }
    //
    template <typename T, typename Allocator>
    vector<T, Allocator>::vector(const vector<value_type> &v)
    {
        m_start = m_allocator.allocate(v.capacity());
        m_finish = m_start;
        m_endofstorage = m_start + v.capacity();
        // copy the elements
        for (size_t i = 0; i < v.size(); i++)
        {
            construct(m_finish, v[i]);
            m_finish++;
        }
    }
    //
    template <typename T, typename Allocator>
    vector<T, Allocator>::vector(const size_t n, const value_type& x)
    {
        m_start = m_allocator.allocate(n);
        m_finish = m_start + n;
        m_endofstorage = m_finish;
        for (size_t i = 0; i < n; i++)
        {
            construct(m_start + i, x);
        }
    }
    //
    template <typename T, typename Allocator>
    template<class InputIt, typename std::enable_if<std::is_pointer<InputIt>::value, int>::type>
    vector<T, Allocator>::vector(InputIt first, InputIt last)
    {
        //size_t n = std::distance(begin, end);
        size_t n = last - first;
        assert(n >= 0);
        m_start = m_allocator.allocate(n);
        m_finish = m_start + n;
        m_endofstorage = m_start + n;
        for (size_t i = 0; i < n; i++)
        {
            construct(m_start + i, *(first + i));
        }
    }
    //
    template<typename T, typename Allocator>
    vector<T, Allocator>::vector(vector &&other) noexcept
    {
        m_start = other.m_start;
        m_finish = other.m_finish;
        m_endofstorage = other.m_endofstorage;
        other.m_start = nullptr;
        other.m_finish = nullptr;
        other.m_endofstorage = nullptr;
    }
    //
    template<typename T, typename Allocator>
    vector<T, Allocator>::vector(std::initializer_list<T> init){
        size_t n = init.size();
        m_start = m_allocator.allocate(n);
        for (size_t i = 0; i < n; i++)
        {
            construct(m_start + i, *(init.begin() + i));
        }
    }
    //
    template <typename T, typename Allocator>
    vector<T, Allocator>::~vector()
    {
        destroy(m_start, m_finish);
        m_allocator.deallocate(m_start);
        m_start = nullptr;
        m_finish = nullptr;
        m_endofstorage = nullptr;
    }
    //

    // other functions
    template<typename T, typename Allocator>
    template <class InputIt, typename std::enable_if<std::is_pointer<InputIt>::value, int>::type>
    void vector<T, Allocator>::assign(InputIt first, InputIt last){
        for(size_t i=0; i<size(); i++){
            destroy(m_start+i);
        }
        m_allocator.deallocate(m_start);
        size_t n = last - first;
        m_start = m_allocator.allocate(n);
        for(size_t i=0; i<n; i++){
            construct(m_start+i,*(first+i));
        }
        m_finish = m_start+n;
        m_endofstorage = m_finish;
    }
    //
    template<typename T, typename Allocator>
    void vector<T, Allocator>::assign(size_type count, const T &value){
        for(size_t i=0; i<size(); i++){
            destroy(m_start+i);
        }
        m_allocator.deallocate(m_start);
        m_start = m_allocator.allocate(count);
        for(size_t i=0; i<count; i++){
            construct(m_start+i,value);
        }
        m_finish = m_start+count;
        m_endofstorage = m_finish;
    }

    // **************************************************
    // capcity and size
    template <typename T, typename Allocator>
    bool vector<T, Allocator>::empty() const
    {
        return m_start == m_finish;
    }
    //
    template <typename T, typename Allocator>
    size_t vector<T, Allocator>::capacity() const
    {
        return m_endofstorage - m_start;
    }
    //
    template <typename T, typename Allocator>
    size_t vector<T, Allocator>::size() const
    {
        return m_finish - m_start;
    }
    //
    template <typename T, typename Allocator>
    void vector<T, Allocator>::resize(size_t newsize, value_type x)
    {
        if (newsize <= size())
        {
            iterator tmp = m_start + newsize;
            destroy(tmp, m_finish);
            m_finish = tmp;
        }
        else if (newsize > capacity())
        {
            reserve(newsize);
            while (m_finish < m_endofstorage)
            {
                construct(m_finish,x);
                m_finish++;
            }
        }
        else
        {
            while (m_finish < m_start + newsize)
            {
                construct(m_finish,x);
                m_finish++;
            }
        }
    }
    //
    template <typename T, typename Allocator>
    void vector<T, Allocator>::reserve(size_t n)
    {
        if (n <= capacity()) {
            return;
        }
        iterator tmp = m_allocator.allocate(n);
        size_t i = 0;
        for (; i < size(); i++)
        {
            construct(tmp + i,m_start[i]);
            destroy(m_start+i);
        }
        m_allocator.deallocate(m_start);
        m_start = tmp;
        m_finish = tmp + i; // we got i as size
        m_endofstorage = tmp + n;
    }
    //
    template<typename T, typename Allocator>
    void vector<T, Allocator>::shrink_to_fit(){
        size_t n = size();
        iterator tmp = m_allocator.allocate(n);
        for(size_t i=0; i<n; i++){
            construct(tmp+i,*(m_start+i));
        }
        for(size_t i=0; i<size(); i++){
            destroy(m_start+i);
        }
        m_allocator.deallocate(m_start);
        m_start = tmp;
        m_finish = tmp + n;
        m_endofstorage = m_finish;
    }

    // ***************************************************************
    // adjust the elements
    template <typename T, typename Allocator>
    void vector<T, Allocator>::pop_back()
    {
        assert(m_start < m_finish);
        destroy(m_finish);
        m_finish--;
    }
    //
    template <typename T, typename Allocator>
    void vector<T, Allocator>::push_back(const value_type &x)
    {
        if (m_finish == m_endofstorage)
        {
            reserve((capacity() == 0) ? 2 : capacity() * 2);
        }
        construct(m_finish,x);
        m_finish++;
    }
    //
    template <typename T, typename Allocator>
    typename vector<T, Allocator>::iterator vector<T, Allocator>::insert(iterator pos, const value_type &x)
    {
        assert(pos <= m_finish);
        assert(pos >= m_start);
        if (m_finish == m_endofstorage)
        {
            size_t n = pos - m_start;
            size_t newcapacity = (capacity() == 0) ? 2 : 2 * capacity();
            reserve(newcapacity);
            pos = m_start + n;
        }
        for (size_t i = 0; i < (m_finish - pos); i++)
        {
            construct(m_finish-i, *(m_finish - i - 1));
        }
        *pos = x;
        m_finish++;
        return pos;
    }
    //
    template<typename T, typename Allocator>
    typename vector<T, Allocator>::iterator vector<T, Allocator>::insert( iterator pos, size_type count, const T& value ){
        assert(pos <= m_finish);
        assert(pos >= m_start);
        if (m_finish + count > m_endofstorage)
        {
            size_t n = pos - m_start;
            size_t newcapacity = size()+count;
            reserve(newcapacity);
            pos = m_start + n;
        }
        // move the elements and construct at the posision
        for (size_t i = 0; i < (m_finish - pos); i++) {
            construct(m_finish + count - i - 1, *(m_finish - i - 1));
        }
        for (size_t i = 0; i < count; i++) {
            construct(pos + i, value);
        }
        m_finish += count;
        return pos;
    }
    //
    template<typename T, typename Allocator>
    template< class InputIt, typename std::enable_if<std::is_pointer<InputIt>::value, int>::type>
    typename vector<T, Allocator>::iterator vector<T, Allocator>::insert( iterator pos, InputIt first, InputIt last )
    {
        assert(pos <= m_finish);
        assert(pos >= m_start);
        size_t count = last-first;
        if (m_finish + count > m_endofstorage)
        {
            size_t n = pos - m_start;
            size_t newcapacity = size()+count;
            reserve(newcapacity);
            pos = m_start + n;
        }
        // move the elements and construct at the posision
        for (size_t i = 0; i < (m_finish - pos); i++) {
            construct(m_finish + count - i - 1, *(m_finish - i - 1));
        }
        for (size_t i = 0; i < count; i++) {
            construct(pos + i, *(first+i));
        }
        m_finish += count;
        return pos;
    }   
    //
    template <typename T, typename Allocator>
    typename vector<T, Allocator>::iterator vector<T, Allocator>::erase(iterator pos)
    {
        size_t n = pos - m_start; 
        assert(pos < m_finish);
        assert(pos >= m_start);
        while (pos < m_finish - 1)
        {
            construct(pos,*(pos + 1));
            pos++;
        }
        destroy(m_finish);
        m_finish--;
        return m_start+n;
    }
    //
    template<typename T, typename Allocator>
    typename vector<T, Allocator>::iterator vector<T, Allocator>::erase( iterator first, iterator last )
    {
        size_t m = first-m_start;
        size_t n = last-first; 
        //assert(first < m_finish);
        assert(n >= 0);
        assert(first >= m_start);
        assert(last < m_finish);
        //assert(last >= m_start);
        iterator pos = first;   
        while (pos < m_finish - n)
        {
            construct(pos,*(pos + n));
            pos++;
        }
        while (pos<m_finish) {
            destroy(pos);
            pos++;
        }
        m_finish-=n;
        return m_start+m;   
    }
    //
    template <typename T, typename Allocator>
    void vector<T, Allocator>::clear()
    {
        destroy(m_start,m_finish);
        m_finish = m_start;
    }
    //
    // template <typename T, typename Allocator>
    // template< class... Args >
    // void vector<T, Allocator>::emplace_back( Args&&... args )
    // {
    //     if (m_finish == m_endofstorage)
    //     {
    //         reserve((capacity() == 0) ? 2 : capacity() * 2);
    //     }
    //     construct(m_finish, std::forward<Args>(args)...);
    //     m_finish++;
    // }
    //
    template <typename T, typename Allocator>
    template< class... Args >
    typename vector<T, Allocator>::reference vector<T, Allocator>::emplace_back( Args&&... args )
    {
        if (m_finish == m_endofstorage)
        {
            reserve((capacity() == 0) ? 2 : capacity() * 2);
        }
        construct(m_finish, std::forward<Args>(args)...);
        T* new_element = m_finish;
        m_finish++;
        return *new_element;
    }

    // ******************************************************
    // new operator
    template <typename T, typename Allocator>
    vector<typename vector<T, Allocator>::value_type> &vector<T, Allocator>::operator=(const vector<value_type> &v)
    {
        if (this != &v)
        {
            size_t n = v.size(); 
            iterator tmp = m_allocator.allocate(n);
            // copy the elements
            for (size_t i = 0; i < n; i++)
            {
                construct(tmp + i, v[i]);
                destroy(m_start + i);
            }
            m_allocator.deallocate(m_start);
            m_start = tmp;
            m_finish = m_start + n;
            m_endofstorage = m_finish;
        }
        return *this;
    }
    //
    template<typename T, typename Allocator>
    vector<typename vector<T, Allocator>::value_type>& vector<T, Allocator>::operator=( std::initializer_list<value_type> ilist )
    {
        size_t n = ilist.size(); 
        iterator tmp = m_allocator.allocate(n);
        // copy the elements
        for (const T& elem : ilist) {
            construct(tmp++, elem);
        }
        for (size_t i=0; i<size(); ++i) {
            destroy(m_start+i);
        }
        m_allocator.deallocate(m_start);
        m_finish = tmp;
        m_start = m_finish - n;
        m_endofstorage = m_finish;
        
        return *this;
    }
    //
    template <typename T, typename Allocator>
    bool vector<T, Allocator>::operator==(const vector<value_type> &v)
    {
        if (v.size() != size())
        {
            return false;
        }
        for (size_t i = 0; i < size(); i++)
        {
            if (*(m_start + i) != v[i])
            {
                return false;
            }
        }
        return true;
    }

    // swap two vectors
    template <typename T, typename Allocator>
    void vector<T, Allocator>::swap(vector<value_type> &v) noexcept
    {
        if (this != &v)
        {
            std::swap(v.m_start, m_start);
            std::swap(v.m_finish, m_finish);
            std::swap(v.m_endofstorage, m_endofstorage);
        }
    }
}

#endif // MYVECTOR_H